1. The Field of the Invention
The present invention relates to font rendering technology; and more specifically, to mechanisms for performing algorithmic simulated emboldening of font characters.
2. Background and Related Art
Computing technology enables a wide-variety of applications. Some of these applications interface with human beings by receiving input from a human user via, for example, a mouse, keyboard, microphone, camera, or the like, or by providing output to a human user via, for example, a speaker, display or printer. In particular, since sight is such a dominant human sensory capability, human users typically rely on some sort of printer or display in order to interpret computational results and/or to interface with an application.
One type of displayed material is characters. Sets of characters (whether it be text or otherwise) may often be logically grouped together. A font represents an example of a logical grouping of characters. In particular, a font is a set of printable or displayable characters in a specific style and size. The characters of the font are often termed “glyphs”.
Characters (glyphs) of a font can be described by outlines or by embedded bitmaps. An outline describes the character by describing the contours of the character shape. Such outlines are more easily scalable. During the rasterization process, software may convert the outline into a bitmap that is suitable for display given the desired point size or Pixels Per EM (ppem).
Embedded bitmaps are usually manually pre-designed bitmap images that correspond to specific ppems. Embedded bitmaps usually are present only for low and middle ppems and for those ppems that usually require higher image quality than those that result from rasterization of unhinted outlines. Hinting is a conditional modification of the outlines which presents another way (compared to embedding bitmaps) of improving quality of the rendered results for low ppems.
Traditionally, characters in fonts with relatively small numbers of characters and relatively simple character shapes (such as Latin) are described by hinted outlines. On the other hand, characters in fonts with large number of characters and relatively complex character shapes (such as East Asian fonts, hereinafter also referred to as EA) are described by unhinted outlines and usually by a series of embedded Black and White bitmaps (hereinafter also referred to as BW). Those more complex fonts usually have embedded bitmaps for some, but not necessarily all, low and middle ppems. Furthermore, the embedded bitmaps do not necessarily cover the full repertoire of the characters in the font. Very rarely, fonts contain Anti-Aliasing (herein after also referred to as AA) embedded bitmaps. Very few, if any, fonts contain embedded bitmaps in CLEARTYPE® (hereinafter also referred to as CT) format.
In some circumstances, it is desirable to “bold” characters. Bolded characters tend to have a heavier visual or typographic weight. Bolded characters are often provided in place of their counterpart regular weight characters. There are a number of instances in which it may be desirable to bold characters. For example, characters are often bolded to emphasize the meaning conveyed by the characters.
A font has a true bold version if there are separate designs of the font characters representing heavier weight and those designs are stored in a way recognizable by the rendering software as being associated with the original font. True bold designs associated with characters of a font do not necessarily follow a uniform bolding transformation with respect to the characters of the original regular weight font. Different elements of the characters are emboldened in the different ways, as appropriate, given the unique form of the character. Often, a human being is involved with the custom design of bolded fonts so as to take into account a host of subjective aesthetic judgments that contribute to a more authentic high quality bolded look.
Traditionally, most commonly-used fonts with smaller numbers of characters and relatively simple character shapes (such as Latin fonts) have associated true bold versions. However, due to the time and cost associated with custom design of fonts, most of the bigger fonts with more complicated characters and larger numbers of characters do not have associated true bold versions. Furthermore, the design of such true bold fonts for these complex character sets can be prohibitively expensive. As a result, if a user chooses a bold option, a simulated emboldening is executed by a rendering engine.
Simulated emboldening is an automatic, algorithmic procedure performed by a rendering engine based on the data from the regular font. Currently applied simulated emboldening is performed by a uniform algorithm that is not always sensitive to the original design intent or to the numerous subjective judgments that improve the quality and appearance of the bolded font data.
Although currently applied algorithms for simulated emboldening provide quite legible results for the fonts with simpler characters, such algorithms usually fail to provide legible results for the fonts with more complex and dense characters.
In a simplified view, the rendering process may be divided into three stages. In the first stage, information from the font file is accessed and, if needed, translated into a rasterizer-readable format. In the second stage, the rasterization process occurs in which the rasterizer-readable font format is converted into a two dimensional-array of values called a bitmap. The bitmap will have one value per pixel for a “simple bitmap”, and more than one value per pixel for an “overscaled bitmap” as is the case for a CLEARTYPE® bitmap. The value may be a simply binary value (e.g., a zero or a one) for a Black and White (BW) bitmap, or a range of values (e.g., from 0 to 16) for an AA bitmap. In the third stage, the actual mapping of the bitmap values to the pixels (or pixel sub-components) of the display occurs resulting in the character being displayed.
Simulated emboldening happens at the second stage during the rasterization process. Although the third stage of mapping the bitmap values to the display may influence the choice of a particular emboldening algorithm and/or tuning the parameters once an algorithm is chosen, particular kinds of mappings can be omitted from the description for clarity in describing the basic principles and embodiments of the present invention. As simulated emboldening algorithms occur during the second stage of rasterization process, the second stage processing will be the primary stage that is discussed herein.
Currently, there are three primary rendering modes; namely, Black and White (BW), Anti-Aliasing (AA) and CLEARTYPE® (CT). Conventionally, at the rasterization stage, the rendering mode defines the final format of the bitmaps and, in particular, the output format of the emboldened bitmaps if emboldening is applied.
There are a variety of factors that may influence a choice of the rendering mode. Such factors may include, for example, device properties and settings, requested ppem, font data (for example, presence of the embedded bitmaps, presence and content of the “gasp” table (as in an OPENTYPE®/TrueType font file)), presence and kind of any geometrical transformation requested. Other factors can influence the choice of the rendering mode. For example, the “complexity” of the font may be considered in choosing the rendering mode. For example, it may be decided to apply BW rendering mode and make use of embedded BW bitmaps for relatively complex fonts and apply CT rendering mode and completely ignore embedded BW bitmaps for relatively less complex fonts.
The choice of rendering mode does not necessary fully realize all the possibilities of the display device. In many situations, the choice is made by software and is based on the general experience of the different rendering modes being more or less legible for the human eyes under different conditions. For example, at low ppem, the AA rendering mode usually provides lower quality rendering results than the BW mode, especially if a font contains BW embedded bitmaps. Therefore, a flag in the “gasp” table can force the BW rendering mode to be applied when rendering low ppem characters, even though the great majority of the display devices can display shades of gray. The same is true regarding CLEARTYPE®. For example, it might be decided to apply BW rendering mode for relatively complex fonts at lower ppems where the embedded BW bitmaps are present in the font, even though the display device has the capability to render in CT mode. The selected rendering mode should provide the best user experience, and can be changed if another rendering mode appears to provide better rendering results.
Currently, regular weight and bold weight characters are commonly rendered in the same rendering mode assuming that all other conditions are the same. However, this decision does not reflect any internal requirements and can be overwritten if another approach will be shown to produce better rendering results.
Current algorithms for bitmap emboldening commonly use the same types of bitmaps for input and output, which means that for an emboldening algorithm, the rendering mode currently implicitly establishes both input and output types. However this dependency is not generically necessary.
The rasterization process goes through the same major steps for the regular and the simulated bold weights. One difference is that if a form of simulated emboldening is applied, an additional emboldening step is used in the rasterization process. This emboldening step intercepts the flow of rasterization as it would be performed for a regular weight, performs necessary emboldening operations, and then lets the flow of the rasterization continue exactly as in the case of a regular weight. Therefore, there will now be some general background description of rasterization for the regular weight so that the emboldening step may be understood in its proper rasterization context.
A rasterizer might accept a lot of different parameters related to specific characteristics of a font or to different rendering conditions being requested. For the purpose of describing the conventional model of simulated emboldening, we will concentrate on the following input information given to a rasterizer:                Information regarding identification of a character being requested (for example a Unicode character code).        Information regarding rendering conditions such as size (ppem), presence of a non-identical geometrical transformation, request for simulated emboldening. If a simulated emboldening is requested, some additional parameters identifying “heaviness” (amount of emboldening) and direction of the emboldening will be passed to the rasterizer (described below in more detail).        Information coming from the font file: such as whether an embedded bitmap is present for a particular character or sum of the characters for the same conditions, access to the description of the embedded bitmap or/and the outline data for a specific character, information specified by designers such as a preferred rendering mode for particular ppems.        Information regarding the rendering mode (which defines the format of the resulting bitmap): specification of the rendering mode BW, AA or CT and any additional required information (for example, in the case of AA emboldening—requested number of gray levels).        
The rasterizer will perform appropriate rasterization based on the input information, and will provide a resulting bitmap in the format corresponding to the requested rendering mode, along with metric information related to the size and positioning of the resulting bitmap.
Since the new algorithms for the emboldening simulation described in the detailed description of the preferred embodiments section below are not intended to necessarily modify the metric information, the bitmap output of the conventional rasterization processes will now be described.
The rasterization process for conventional BW rendering will now be described with respect to a specific example and with respect to FIG. 1. In the BW rendering mode, a rasterizer will usually use the embedded BW bitmap if present. In the example of FIG. 1, suppose that the Unicode “GREEK CAPITAL LETTER MU” is to be rendered. If there is a BW bitmap for the character and requested conditions (in FIG. 1, branch “(BW: Embedded BW Simple Bitmap)”), then the embedded BW bitmap is used for rasterization. The BW values from the rasterizer are then mapped to the actual pixel colors by software outside of the rasterizer.
If there is not a BW bitmap for the character and requested conditions (in FIG. 1, branch “(BW: Outline to Simply Bitmap)”), then a simple bitmap is rendered using the outline information present in the font by applying a scan-conversion algorithm to the outline. The reason that an embedded bitmap is used if present is that for unhinted fonts, a bitmap produced by rendering of an outline usually has lower quality than an embedded bitmap.
Whichever approach is being used, the final output has the same format: simple BW bitmap. An important characteristic of this rasterization process is that it does not use overscaled bitmaps at any intermediate steps of computation of the final output bitmap. There is only one value per pixel at all stages of the computation.
The rasterization process for conventional AA rendering will now be described with respect to a specific example and with respect to FIGS. 2A and 2B. In AA rendering mode, a rasterizer usually uses an embedded AA bitmap if present (in FIG. 2A, branch “(AA: Embedded AA Simple Bitmap)”) in a font to be rendered. Since almost no fonts have embedded AA bitmaps, branch (AA: Embedded AA Simple Bitmap) is almost never executed.
On the other hand, if an embedded bitmap is not present for a character and requested conditions, a simple AA bitmap is rendered using the outline information present in the font (in FIG. 2A, branch “(AA: Outline to Overscaled Bitmap)” continuing in FIG. 2B to branch “(AA: Overscaled to Simple Bitmap)”. When rasterization starts from the outline information, rasterization proceeds through two independent stages: (AA: Outline to Overscaled Bitmap) and (AA: Overscaled to Simple Bitmap). The algorithm for computation of the overscaled bitmap based on the outline data used during stage (AA: Outline to Overscaled Bitmap) and algorithm for computation of the final values of the simple AA bitmap during stage (AA: Overscaled to Simple Bitmap) do not depend on each other, and can be modified independently as long as they work with the required input and output formats.
Whichever approach is being used, the final output has the same format: simple AA bitmap. An important characteristic of this rasterization process is that when there is no embedded AA bitmap, the rasterization process uses an overscaled bitmap as an intermediate result of computation of the final output bitmap.
Now that the rasterization process has been described generally for each of the BW and AA rendering modes, the description proceeds to conventional BW and AA emboldening algorithms. Depending on the type of input, algorithms for the emboldening simulation are subdivided into two large groups: “bitmap emboldening” and “outline emboldening”. In addition to the various emboldening parameters, a bitmap emboldening algorithm accepts a bitmap as its input, while an outline emboldening algorithm accepts an outline as its input. Bitmap emboldening returns a bitmap as its output, while outline emboldening returns a modified outline, which later will be scan-converted in order to produce a bitmap.
Bitmap and outline emboldening algorithms are applied at different stages of the rasterization process. Outline emboldening will be always applied before the first step of the rasterization process as it would be performed for a regular weight. After an outline emboldening is performed, the rasterization will continue exactly as it would in the case of a regular weight.
Currently, outline emboldening is almost never applied. Bitmap emboldening is performed by most of the applications in most situations, except in the rare cases when a non-trivial geometrical transformation is applied to a text. The capability of applying bitmap emboldening does not depend on the character having an embedded bitmap. Bitmap emboldening can thus be applied to characters that either have, or do not have, an embedded bitmap. If the character does not have an embedded bitmap for the requested condition, the result of scan-conversion based on the outline information will serve as an input for a bitmap emboldening algorithm. The principles of the present invention apply more to bitmap emboldening and thus several conventional bitmap emboldening algorithms will now be described.
By definition, bitmap emboldening algorithms accept bitmaps as their input and return bitmaps as their output. In addition to the bitmap itself, a bitmap emboldening algorithm usually accepts information regarding heaviness and direction of emboldening. This information can be expressed by a pair of “emboldening shifts” in the horizontal and vertical directions respectively. An emboldening shift identifies by which amount (expressed in pixels) an emboldened bitmap should be visually heavier than the original one and a sign of a shift shows the direction (to the right/to the left and to the top/to the bottom) of the emboldening. Most of the current applications work with emboldening shifts corresponding to the whole numbers of pixels only. In addition, at low/middle and even at the lower range of high ppems (e.g., up to about 50 ppem), simulated emboldening by 1 pixel to the right (and 0 pixels in the vertical direction) is usually applied.
The input bitmap can originate from different data (such as embedded bitmap or a glyph's outline) and can be computed in different ways. The particular way the input bitmap is computed is irrelevant for the emboldening algorithm that is applied to the bitmap. What matters is which format of an input bitmap is expected by an emboldening algorithm and which format of an output bitmap the algorithm will generate. The various emboldening algorithms will thus be distinguished based on the format of the input and output bitmaps.
Different kinds of bitmap emboldening algorithms can be applied at different steps of the rasterization process since different steps of the rasterization process work with bitmaps in different formats. However currently applied bitmap emboldening algorithms often start with simple bitmaps (in BW, AA or CT format) and generate simple bitmaps in the same format as their input.
Most of the currently applied bitmap emboldening algorithms work with simple bitmaps both as input and output, even during a rasterization process that involves computation of overscaled bitmaps. If overscaled bitmaps are computed, emboldening is applied after the overscaled bitmap is converted into a simple bitmap.
In addition, most of the currently applied bitmap emboldening algorithms have exactly the same output bitmap format as the input bitmap format.
Furthermore, the algorithms often turn on or make darker some of the pixels that were off or had lighter colors in the input bitmap, and often do not turn off pixels or make them lighter.
Also, conventional algorithms typically decide whether to modify a value of a specific pixel based on the local characteristics of the input bitmap, such as one (for low/middle ppems) or several neighboring pixels in the direction of the emboldening. Currently used algorithms do not use information of the neighboring pixels in the direction perpendicular to the emboldening.
Moreover, conventional algorithms work row-by-row (for horizontal emboldening) and column-by-column (for vertical emboldening) and, therefore, the algorithms analyze only one direction (either horizontal or vertical) at a time. In other words, the resulting value of a pixel depends on neighbors of a pixel either in the row only or in the column only and does not take into account a two-dimensional neighborhood.
Currently applied bitmap emboldening algorithms can be applied in the horizontal or vertical direction. Algorithms for horizontal and vertical directions are essentially symmetric, with change of the directionality only. Generally, the algorithms for horizontal and vertical emboldening do not intermix. In other words, if the emboldening should be applied in both directions, then it will first be applied in one direction and then applied in another direction to the result of the emboldening in the first direction.
Furthermore, besides the rectangular pixel area containing the input bitmap, the algorithms usually affect one or several rows and/or one or several columns adjacent to the rectangular area, depending on the values of the emboldening shifts accepted as the parameters.
For low/middle ppems (i.e., up to about 50 ppem), the algorithms usually apply emboldening by 1 pixel in the horizontal direction to the right. Note, that the low/middle ppems are exactly the area where the quality of the rendered images is especially challenging and where an improvement of the existing algorithms is especially required.
As illustrated by FIG. 3A, in BW rendering mode, a conventional emboldening algorithm accepts a BW simple bitmap as an input, and generates a BW simple bitmap as an output. The emboldening algorithm is performed at the end of the rendering process as it would be applied in the case of a regular weight (see, for example, FIG. 1 of this description).
Specifically, if an embedded bitmap is present in the font for the requested condition (YES in FIG. 3A), the BW emboldening algorithm also called hereinafter “(BW: Bitmap Simple Regular to Bitmap Simple Bold)” is applied to the output bitmap of the step called hereinafter “(BW: Embedded BW Simple Bitmap)” (see left half of FIG. 1). Alternatively, if an embedded bitmap is not present in the font for the requested condition (NO in FIG. 3A), the step (BW: Bitmap Simple Regular to Bitmap Simple Bold) is performed after the step called hereinafter “(BW: Outline to Simple Bitmap)” (see right half of FIG. 1) if the rasterization is based on the outline data.
The requirement in (BW: Bitmap Simple Regular to Bitmap Simple Bold) for both input and output bitmaps to be BW simple bitmaps is quite inflexible. Subject to these restrictions, the emboldening algorithm can only turn on (i.e. assign value 1 to) some of the pixels in the output bitmap that were turned off (had value 0) in the input bitmap.
For example, in the case when a bitmap should be emboldened by 1 pixel to the right in the horizontal direction, a commonly used algorithm called herein “<BW: Alg Standard>” works as follows. For every row in the original bitmap, turn on all the pixels that have a “black” (i.e., turned on) immediate left neighbor.
An example of application of the algorithm is shown in both FIGS. 3B and FIG. 3C, in which the input and output of the algorithm are shown after a mapping to black and white colors by software external to the rasterizer. As can be seen from FIG. 3B, the algorithm <BW: Alg Standard> performs a completely reasonable operation considering the restrictions. However, the character in FIG. 3C is rendered using the same emboldening algorithm. As apparent from FIG. 3C, the emboldening algorithm causes the output character to become unrecognizable if the character is relatively complex.
As illustrated by FIG. 4A, in AA rendering mode, conventional emboldening algorithms accepts an AA simple bitmap as an input and generates an AA simple bitmap as an output. The emboldening algorithm waits till the end of rendering process as it would be applied in the case of a regular weight. Specifically, for rendering of a character that has an AA bitmap for a requested condition (YES in FIG. 4A), a simple AA bitmap is generated based on the embedded AA bitmap data as represented in the step (AA: Embedded AA Simple Bitmap) (see, left half of FIG. 2A). On the other hand, for rendering of a character that does not have an AA bitmap for the requested condition (NO in FIG. 4A), a simple AA bitmap is generated using steps (AA: Outline To Overscaled Bitmap) and (AA: Overscaled to Simple Bitmap) (see the right half of FIG. 2A) based on the outline of the character. In either case, the AA emboldening step called hereinafter “(AA: Bitmap Simple Regular to Bitmap Simple Bold)” is applied to the output bitmap.
A conventional AA emboldening algorithm called hereinafter “<AA: Alg Standard>” operates on the simple AA bitmap, which, for every pixel, represents the number of turned on subpixels in the overscale bitmap. The algorithm works according to a simple “additive” principle, accumulating numbers of turned on subpixels for the adjacent pixels. The algorithm does not work with exact positions of subpixels inside a pixel, but rather with the cumulative information regarding the number of turned on subpixels within a pixel.
Although the algorithm works with these cumulative values only, the results are quite similar to the simplest algorithm that would work directly on the overscaled bitmap uniformly emboldening the overscaled bitmap by the number of subpixels in a pixel, which provides a reasonable justification for the conventional algorithm. The problem is, however, that for more complex characters, the current algorithm does not produce legible results.
For emboldening by 1 pixel to the right, a conventional AA emboldening algorithm <AA: Alg Standard> is as follows:                1) For every row in the original bitmap, proceed from right to the left.        2) For every pixel:                    2a) Add a value of the immediate left neighbor to the value of the pixel itself.            2b) If the resulting value exceeds the maximal value allowed in the specific format, assign the maximal value to the pixel.                        
An example of the application of the algorithm is shown in FIG. 4B. This example continues the example related to the “wave” character given above (in FIGS. 2A and 2B) with relation to the rendering in AA mode for a regular weight.
Accordingly, what would be advantageous are BW and AA simulated emboldening mechanisms in which the emboldened character is more legible and readable, even for complex characters.